#include <bits/stdc++.h>
#define __NO_MAIN__ false
constexpr bool MTS = true, SPC_MTS = false;
#define FULL(arg) begin(arg), end(arg)
#define ALL(arg, l, r) begin(arg) + l, begin(arg) + r + 1

// :/

using namespace std;
using tp = long long int;
[[maybe_unused]] constexpr tp ZERO = 0, ONE = 1, INF = -1ull >> 3;
int WITHERING(unsigned long long int);
void MIST();

#if !__NO_MAIN__
int main(int argc,char* argv[]){unsigned long long int t=0,_t=1;if(MTS&&!SPC_MTS
) cin >>_t;MIST();while(t<_t||SPC_MTS){if(WITHERING(++t)!=0)return 0;}return 0;}
#endif
template <typename _Ty> class _Lambda_t {_Ty lexp;public:template<typename __Ty>
_Lambda_t(__Ty&&lexp):lexp(static_cast<__Ty&&>(lexp)){}template<typename... __Ty
>decltype(auto)operator()(__Ty&&...args){return lexp(std::ref(*this),static_cast
<__Ty&&>(args)...); } }; template <typename _Ty> decltype(auto) lexp(_Ty&&l_exp)
{ return _Lambda_t<typename std::decay<_Ty>::type>(static_cast<_Ty&&>(l_exp)); }
template <typename _Ty1, typename _Ty2> bool ckmax(_Ty1& a, const _Ty2& b) { if(
a<b){a=b; return true; } return false; } template <typename _Ty1, typename _Ty2>
bool ckmin(_Ty1&a,const _Ty2&b){if(b < a) { a = b; return true; } return false;}
#ifdef XCODE
#define bg(...){cout<<"["<<__LINE__<<'@'<<++_LT[__LINE__]<<':';BG(__VA_ARGS__);}
size_t _LT[21777]; template<typename _Type>void BG(const _Type&_cur){cout<<' '<<
_cur << ']' <<" <<:"<<std::endl;}template<typename _Type,typename... _Other>void
BG(const _Type& _cur, const _Other& ..._other) {cout<< ' '<<_cur;BG(_other...);}
#else
#define bg(...)
#endif

// :/

// :/

tp c;
struct STRUGGLE {
   STRUGGLE() {
      freopen("oi.in", "r", stdin), freopen("oi.out", "w", stdout);
      cin.tie(nullptr)->sync_with_stdio(false);
      cin >> c;
   }
   
   ~STRUGGLE() {
   }
} STRUGGLE;

void MIST() {
}

constexpr tp mod = 998244353ll;
tp norm(tp x) { return x + (x < 0) * mod - (x >= mod) * mod; }
void add(tp &x, tp y) { x = norm(x + y); }
tp pow(tp x, tp y) {
   tp z = 1;
   for (; y; x = x * x % mod, y >>= 1ll)
      if (y & 1ll) z = z * x % mod;
   return z;
}

namespace RCAL { vector<tp> fact, ifac; tp MOD;template <typename Ty> void exgcd
(Ty a, Ty b, Ty& x, Ty& y) {if(b!=0){exgcd(b,a%b,y,x);y-=a/b*x;}else{x=1;y=0;}};
template<typename T>T inv(T num,T mod=MOD){T x,y;exgcd(num,mod,x,y);return x<0?x
+mod:x;}template<typename Ty>Ty mul(Ty x, Ty y,Ty mod=MOD){Ty tar=0;while(y){if(
y&1)tar=(tar+x)%mod;x=x*2%mod;y/=2;}return tar;}template<typename Ty>Ty pow(Ty x
, Ty y,Ty mod=MOD){Ty tar=1;while(y){if(y&1)tar=tar*x%mod;x=x*x%mod;y/=2;}return
tar;}void init(tp n,tp mod){MOD=mod;fact.resize(n+1);ifac.resize(n+1);fact[0]=1;
for(tp i = 1; i <= n; ++i) fact[i] = fact[i - 1] *i%mod;ifac[n]=inv(fact[n]);for
(tp i = n - 1; i >= 0; --i) ifac[i] = ifac[i +1]*(i+1)%mod;}tp binom(tp n,tp m){
if (n < m || m < 0) return 0; return fact[n] * ifac[m] % MOD * ifac[n - m]%MOD;}
}  // RCAL RCAL

int WITHERING([[maybe_unused]] unsigned long long int TEST_NUMBER) {
   tp n, m; cin >> n >> m;
   vector<tp> x(m + 1, 0), y(m + 1, 0);
   for (tp i = 1; i <= m; ++i) cin >> x[i] >> y[i];
   auto work1 = [&] () -> void {
      vector<pair<tp, tp>> e;
      for (tp i = 1; i <= n; ++i)
         for (tp j = i + 1; j <= n; ++j) e.emplace_back(i, j);
      vector<vector<tp>> d(n + 1, vector<tp>(n + 1));
      tp t = e.size();
      tp ans = INF, cnt = 0;
      for (tp s = 0; s < 1 << t; ++s) {
         if (__builtin_popcount(s) != m - 1) continue;
         d.assign(n + 1, vector<tp>(n + 1, INF));
         for (tp i = 0; i < t; ++i) {
            if (s & (1 << i)) {
               auto [u, v] = e[i];
               d[u][v] = d[v][u] = 1;
            }
         }
         for (tp i = 1; i <= n; ++i) d[i][i] = 0;
         for (tp k = 1; k <= n; ++k)
            for (tp i = 1; i <= n; ++i)
               for (tp j = 1; j <= n; ++j) ckmin(d[i][j], d[i][k] + d[k][j]);
         tp cur = 0;
         for (tp i = 1; i <= m; ++i) cur += d[x[i]][y[i]];
         if (cur == ans) cnt++;
         else if (cur < ans) ans = cur, cnt = 1;
      }
      cout << -ans << ' ' << cnt << "\n";
      return ;
   };
   if (n <= 5) return work1(), 0;
   RCAL::init(3 * n + 2, mod);
   cout << -2 * (n - 1) << ' ' << RCAL::binom(3 * n, n) * pow(2 * n + 1, mod - 2) % mod << "\n";
   return 0;
}

// :\ */

